高考申論題
109年
[資訊處理] 資料結構
第 一 題
📖 題組：
四、若我們用相鄰矩陣（Adjacency Matrix）M來表示圖一中的無向圖G = (V, E)，請考慮下面的問題：
圖一、無向圖G = (V, E)
四、若我們用相鄰矩陣（Adjacency Matrix）M來表示圖一中的無向圖G = (V, E)，請考慮下面的問題：
圖一、無向圖G = (V, E)
對於無向圖G = (V, E)：（12分）
⑴請給出對應的相鄰矩陣M。
⑵以字母順序為考量進行深度優先搜尋（Depth-First Search, DFS），請由節點a開始，描述此深度優先搜尋所產生的深度優先樹（DF-tree）。
⑴請給出對應的相鄰矩陣M。
⑵以字母順序為考量進行深度優先搜尋（Depth-First Search, DFS），請由節點a開始，描述此深度優先搜尋所產生的深度優先樹（DF-tree）。
📝 此題為申論題
思路引導 VIP
解答本題分為兩部分：首先，依據圖中節點的連線關係，以英文字母順序排列行列，建構 8x8 的相鄰矩陣（無向圖的矩陣必為對稱矩陣）。其次，進行 DFS 追蹤時，務必嚴格遵守「遇到分岔點時依字母順序挑選尚未拜訪之節點」的規則，並詳細記錄每次前進產生的「樹邊（Tree Edge）」與無路可走時的「回溯（Backtracking）」過程，最後畫出完整的深度優先樹。
🤖
AI 詳解
AI 專屬家教
【解題思路】 本題測驗圖的基礎表示法與走訪演算法。第一子題須將圖轉換為相鄰矩陣；第二子題須利用堆疊（或遞迴）概念執行深度優先搜尋（DFS），並依據題目要求的「字母順序」作為分支選擇條件，以建構出唯一的深度優先樹。 【詳解】
▼ 還有更多解析內容
圖的矩陣表示與走訪
💡 運用相鄰矩陣表示圖結構，並依循 DFS 邏輯與特定權重順序生成樹。
| 比較維度 | 深度優先搜尋 (DFS) | VS | 廣度優先搜尋 (BFS) |
|---|---|---|---|
| 輔助資料結構 | 堆疊 (Stack) 或遞迴 | — | 佇列 (Queue) |
| 搜尋策略 | 一條路走到底再回溯 | — | 層層向外擴散 |
| 典型應用 | 尋找路徑、拓撲排序 | — | 單位權重最短路徑 |
💬DFS 著重於深度探索與回溯機制，BFS 著重於水平分層掃描。
